#include "thread.h"
ThreadNode *BuyTreeNode(DataType val)
{
    ThreadNode *newnode = (ThreadNode *)malloc(sizeof(ThreadNode));
    if (newnode == NULL)
    {
        perror("malloc fail");
        return NULL;
    }
    newnode->data_ = val;
    newnode->left_ = newnode->right_ = NULL;
    newnode->lflag_ = newnode->rflag_ = 0;
    return newnode;
}
ThreadTree Create()
{
    ThreadNode *n1 = BuyTreeNode(1);
    ThreadNode *n2 = BuyTreeNode(2);
    ThreadNode *n3 = BuyTreeNode(3);
    ThreadNode *n4 = BuyTreeNode(4);
    ThreadNode *n5 = BuyTreeNode(5);
    ThreadNode *n6 = BuyTreeNode(6);
    n1->left_ = n2;
    n1->right_ = n3;
    n2->left_ = n4;
    n2->right_ = n5;
    n3->right_ = n6;
    return n1;
}
void inorder(ThreadTree root)
{
    if (root == NULL)
        return;
    if (root->lflag_ == 0)
        inorder(root->left_);
    printf("%d ", root->data_);
    printf("[lflag=%d,rflag=%d] ", root->lflag_, root->rflag_);
    if (root->rflag_ == 0)
        inorder(root->right_);
}
void Destory(ThreadTree *root)
{
    if (*root == NULL)
        return;
    Destory(&((*root)->left_));
    Destory(&((*root)->right_));
    free(*root);
    *root = NULL;
}
// 中序线索化
void InThread(ThreadTree root, ThreadNode **prev)
{
    if (root == NULL)
        return;
    InThread(root->left_, prev);
    if (root->left_ == NULL)
    {
        root->left_ = *prev;
        root->lflag_ = 1;
    }
    if ((*prev) != NULL && (*prev)->right_ == NULL)
    {

        (*prev)->right_ = root;
        (*prev)->rflag_ = 1;
    }
    *prev = root;
    // printf("%d ", root->data_);
    InThread(root->right_, prev);
}
void CreateInThread(ThreadTree root)
{
    ThreadNode *prev = NULL;
    InThread(root, &prev);
    prev->right_ = NULL;
    prev->rflag_ = 1;
    // inorder(root);
}

// 前序线索化
void PreThread(ThreadTree root, ThreadNode **prev)
{
    if (root == NULL)
        return;
    if (root->left_ == NULL)
    {
        root->left_ = *prev;
        root->lflag_ = 1;
    }
    if ((*prev) != NULL && (*prev)->right_ == NULL)
    {
        (*prev)->right_ = root;
        (*prev)->rflag_ = 1;
    }
    (*prev) = root;
    // printf("%d ", root->data_);
    if (root->lflag_ == 0)
        PreThread(root->left_, prev);
    PreThread(root->right_, prev);
}
void CreatePreThread(ThreadTree root)
{
    ThreadNode *prev = NULL;
    PreThread(root, &prev);
    prev->rflag_ = 1;
    // inorder(root);
}

// 后序线索化
void Lasthread(ThreadTree root, ThreadNode **prev)
{
    if (root == NULL)
        return;
    Lasthread(root->left_, prev);
    Lasthread(root->right_, prev);
    if (root->left_ == NULL)
    {
        root->left_ = (*prev);
        root->lflag_ = 1;
    }
    if ((*prev) != NULL && (*prev)->right_ == NULL)
    {
        (*prev)->right_ = root;
        (*prev)->rflag_ = 1;
    }
    (*prev) = root;
    // printf("%d ", root->data_);
}
void CreateLastThread(ThreadTree root)
{
    ThreadNode *prev = NULL;
    Lasthread(root, &prev);
    if (prev->right_ == NULL)
        prev->rflag_ = 1;
    // inorder(root);
}

/////////////////////

// 中序线索树的正向遍历
// ThreadNode *FindLeftNode(ThreadTree root)
// {
//     while (root->lflag_ != 1)
//         root = root->left_;

//     return root;
// }
// ThreadNode *NextNode(ThreadNode *tmp)
// {
//     if (tmp->rflag_ == 1)
//         return tmp->right_;
//     else
//         return FindLeftNode(tmp->right_);
// }
// void ThreadInOrder(ThreadTree root)
// {

//     for (ThreadNode *tmp = FindLeftNode(root); tmp != NULL; tmp = NextNode(tmp))
//     {
//         printf("%d\n", tmp->data_);
//     }
// }
// 中序线索树的逆向遍历
// ThreadNode *FindrightNode(ThreadTree root)
// {
//     while (root->rflag_ != 1)
//         root = root->right_;

//     return root;
// }
// ThreadNode *PreNode(ThreadNode *tmp)
// {
//     if (tmp->lflag_ == 1)
//         return tmp->left_;
//     else
//         return FindrightNode(tmp->left_);
// }
// void ThreadReverseInOrder(ThreadTree root)
// {

//     for (ThreadNode *tmp = FindrightNode(root); tmp != NULL; tmp = PreNode(tmp))
//     {
//         printf("%d\n", tmp->data_);
//     }
// }
// 先序线索树的顺序遍历
// ThreadNode *NextNode(ThreadNode *root)
// {
//     if (root->rflag_ == 1)
//         return root->right_;
//     else
//     {
//         if (root->lflag_ == 0)
//             return root->left_;
//         else
//         {
//             return root->right_;
//         }
//     }
// }
// void ThreadPreOrder(ThreadTree root)
// {
//     for (ThreadNode *tmp = root; tmp; tmp = NextNode(tmp))
//     {
//         printf("%d ", tmp->data_);
//     }
// }
// 后序线索树的逆向遍历
// ThreadNode *LastNode(ThreadNode *root)
// {
//     while (root->lflag_ != 1 && root->rflag_ != 1)
//     {
//         while (root->lflag_ != 1)
//             root = root->left_;
//         while (root->rflag_ != 1)
//             root = root->right_;
//     }
//     return root;
// }
ThreadNode *PreNode(ThreadNode *root)
{
    if (root->lflag_ == 1)
        return root->left_;
    else
    {
        if (root->rflag_ == 0)
            return root->right_;
        else
        {
            return root->left_;
        }
    }
}
void ThreadLastOrder(ThreadTree root)
{
    for (ThreadNode *tmp = root; tmp; tmp = PreNode(tmp))
    {
        printf("%d ", tmp->data_);
    }
}